package leetcode_1_200;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_120_2_timeout {
    public static void main(String[] args) {
        List<List<Integer>> tes = new ArrayList<>();
        ArrayList<Integer> l1 = new ArrayList<>();
        l1.add(2);
        tes.add(l1);
        ArrayList<Integer> l2 = new ArrayList<>();
        l2.add(3);
        l2.add(4);
        tes.add(l2);
        ArrayList<Integer> l3 = new ArrayList<>();
        l3.add(6);
        l3.add(5);
        l3.add(7);
        tes.add(l3);
        ArrayList<Integer> l4 = new ArrayList<>();
        l4.add(4);
        l4.add(1);
        l4.add(8);
        l4.add(3);
        tes.add(l4);
        System.out.println(minimumTotal(tes));
    }

    private static int minimumTotal(List<List<Integer>> triangle) {
        int depth = triangle.size() - 1;
        List<Integer> list = triangle.get(depth);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i++) {
            res = Math.min(res, f(triangle, depth, i));
        }
        return res;
    }

    private static int f(List<List<Integer>> triangle, int depth, int index) {
        if (depth == 0)
            return triangle.get(0).get(0);
        List<Integer> list = triangle.get(depth);
        int res;
        if (index - 1 >= 0 && index != list.size() - 1){
            res = list.get(index) + Math.min(f(triangle, depth - 1, index),
                    f(triangle, depth - 1, index - 1));
        }else if (index - 1 < 0){
            res = list.get(index) + f(triangle, depth - 1, index);
        }else {
            res = list.get(index) + f(triangle, depth - 1, index - 1);
        }
        return res;
    }
}
